#include "LinklistwithHead.h"

Head *createList()
{
    //开辟管理者节点空间,并且初始化
    Head *ph = (Head *)malloc(sizeof(Head));
    ph->first = NULL;
    ph->last = NULL;
    ph->nodenum = 0;
    return ph;
}

void insertToList(Datatype num,Head *h)
{
     if(h == NULL)
    {
        printf("链表不存在!\n");
        return ;
    }
    //为num分配一个节点空间
    Node *pnew = (Node *)malloc(sizeof(Node));
    pnew->data = num;
    pnew->next = NULL;
    //把节点加入到h管理的链表
    if(h->first == NULL)  //当前链表中还没有数据节点
    {
        h->first = pnew;
        h->last = pnew;
    }else 
    {
/*
        //头插法
        //pnew->next = h->first;
        //h->first = pnew;
        
        //尾插法
        h->last->next = pnew;
        h->last = pnew;
*/
        //建立有序链表
        if(pnew->data <= h->first->data)   //新节点比第一个节点数据小-->头插法
        {
            pnew->next = h->first;
            h->first = pnew;
        }
        else if(pnew->data >= h->last->data)   //新节点比最后一个节点数据大-->尾插法
        {
            h->last->next = pnew;
            h->last = pnew;
        }else 
        {
            //找一个插入位置
            Node *p = h->first;     //指向第一个比pnew大的节点
            Node *pr = h->first;    
            while(p)
            {
                if(p->data > pnew->data)
                {
                    break;
                }
                pr = p;
                p = p->next;
            }
            //p就指向第一个比pnew大的节点,应该把数据放到p的前面
            pr->next = pnew;
            pnew->next = p;
        }

    
    }
    h->nodenum++;
}

void printList(Head *h)
{
     if(h == NULL)
    {
        printf("链表不存在!\n");
        return ;
    }
    printf("Node nodenum:%d\n",h->nodenum);
    printf("Node Data:   ");
    Node *p = h->first;
    while(p)
    {
        printf("%d  ",p->data);
        p = p->next;
    }
    printf("\n");
}

void clearList(Head *h)
{
    if(h == NULL  || h->first == NULL)  //链表不存在或者链表中没有数据节点
    {
        return ;
    }

    //一个一个的释放数据节点
    while(h->first)  //还拥有数据节点
    {
        Node *p = h->first;
        h->first = p->next;
        p->next = NULL;
        free(p);
        h->nodenum--;
    }
    h->last = NULL;
}

void deleteList(Head *h)
{
    //清空整个链表
    clearList(h);
    //释放头结点
    free(h);
}


/*
1.写一个函数,可以根据一个数字字符串建立一个链表,链表中逆序存储各个位上的数字
    如:
    char *str = 123456789;
    链表上的节点:
        9 8 7 6 5 4 3 2 1 
    Head *createListByStr(char *str)
    {
        //先创建链表

        //遍历字符串,把字符串中的每一个字符转换成数字加入链表

        //返回创建好的链表的头结点
    }
*/
Head *createListByStr(char *str)
{
    //创建头结点head
    Head *head = (Head *)malloc(sizeof(Head));
    head->first = NULL;
    head->last = NULL;
    head->nodenum = 0;

    //scanf输入字符串
    //如果字符串为空的情况
        if(str ==NULL || *str == '\0')
        {
            return head;//返回空链表
        }
    //while循环
    while(*str)
    {
        
        //int n = 0;
        Node *pnew = (Node *)malloc(sizeof(Node));
        pnew->data = *str-'0';// 将字符转换为数字，+即可反向转换
        pnew->next = NULL;
        //将字符str[x]赋值给pnew->data,并且pnew的data和next不断刷新
        //同时开始插入-头插法
        if(head->first == NULL)//从无到有
        {
            head->first = pnew;
            head->last = pnew;
        }
        else//将str的字符给到pnew->data中，并且使用头插法
        {
            pnew->next = head->first;
            head->first = pnew;
        }
        str++;
        head->nodenum++;
    }
    return head;
}



/*
2.使用链表逆序存储两个数字字符串中的数字,实现两个超大数的加法
    如:
    char *str1 = 123456789;
    链表1:
    9 8 7 6 5 4 3 2 1

    char *str2 = 987654321;
    链表2:
    1 2 3 4 5 6 7 8 9 

    返回的链表:
    1111111110

    Head *addTwoBigNum(Head *h1,Head* h2)
    {

    }
*/
 Head *addTwoBigNum(Head *h1,Head *h2)
 {
    //创建头结点head
    Head *head = (Head *)malloc(sizeof(Head));
    head->first = NULL;
    head->last = NULL;
    head->nodenum = 0;

    Node *p1 = h1->first;
    Node *p2 = h2->first;
    int carry = 0;
    int sum = 0;
    //scanf输入字符串
    //如果字符串为空的情况
        
    //while循环
    while(p1 != NULL || p2 != NULL || carry)
    {
        sum = carry;
        //问题大小端混乱
        //因为还属于单链表，而h1->first无法获得进位
        //完成进位问题
        //字符串相加：字符串先反转，个位先加，进位，利用头插法进位
        printf("aaaaaaaaaaaa\n");
        if(p1 != NULL)
        {
            sum+= p1->data;
            p1 = p1->next;
        }
        if(p2 !=NULL)
        {
            sum+= p2->data;
            p2 = p2->next;
        }
        carry = sum/10;
        sum = sum%10;
        printf("bbbbbbbbbbbb\n");
        Node *pnew = (Node *)malloc(sizeof(Node));
		pnew->data = sum;
        pnew->next = NULL;
        //将字符str[x]赋值给pnew->data,并且pnew的data和next不断刷新
        //同时开始插入-头插法
        printf("cccccccccc\n");
        if(head->first == NULL)//从无到有
        {
            head->first = pnew;
            head->last = pnew;
        }
        else//将str的字符给到pnew->data中，并且使用头插法
        {
            pnew->next = head->first;
            head->first = pnew;
        }
		//h1->first = h1->first->next;
		//h2->first = h2->first->next;
        head->nodenum++;
    }
    return head;
 }

/*
3.归并两个有序链表(利用原有空间),使得归并之后的链表任然有序
*/

void Meger_LinkedListWithHead(Head *h1,Head *h2)
{
    //新建一个链表C
    Head *C = createList();
    //建立一个pnew，指向要拆下来的节点
    Node *pnew = NULL;
    while(h1->first && h2->first)//开始循环（AB都纯在）
    {
         //比较AB大小
         if(h1->first <= h2->first)//A小：A开始，结果来的C要与A后续断开
         {
            pnew = h1->first;
            h1->first = h1->first->next;
            pnew->next = NULL;
         }
         else//B小，B开始
         {
            pnew = h2->first;
            h2->first =h2 ->first->next;
            pnew->next = NULL;
         }
        if(C->first == NULL)//从无到有
        {
            C->first = pnew;
            C->last = pnew;
        }
        else //从少到多
        {
            //尾插法
            C->last->next = pnew;
            C->last = pnew;
        }
    } 
    //AB有一个结束，判断还剩哪个，全全接收
    if(h1->first == NULL)//如果A结束，B还有
    {
        C->last->next = h2->first;
        C->last = h2->last;
    }
    else
    {
        C->last->next = h1->first;
        C->last = h1->last;
    }
    /*step5释放A,B的头结点*/
	h1->first = NULL;
	h1->last = NULL;
	h2->first = NULL;
	h2->last = NULL;
	free(h1);
	free(h2);
}